#include "erode_cond_detail.h"
#include <vector>
#include <queue>

namespace boost {
namespace gil {
namespace extension {
namespace filters {
namespace morph {
namespace detail {

typedef struct point_s {
    point_s(int x, int y) : x(x), y(y) {}
    int x;
    int y;
} point_t;

const int SIZE_NOT_COMPUTED_YET = -2;
const int SIZE_NOT_AVAILABLE = -1; // for black pixels
const int SIZE_BEING_PROCESSED = 0;

const base_filter::gray_level_t BLACK = 0;
const base_filter::gray_level_t WHITE = 255;

// used to transition from given row, col to each of the
// 4 different directions
//int dr[] = { 0, -1, 1, 0 };
//int dc[] = { -1, 0, 0, 1 };

int dr[] = { -1, 1, -1, 1, 0, -1, 1, 0 };
int dc[] = { -1, 1, 1, -1, -1, 0, 0, 1 };

size_lookup::size_lookup(const base_filter::image_t::const_view_t& view) : view(view), sizes(boost::extents[view.height()][view.width()]) {
    for (int y = 0, h = view.height(); y < h; y++) {
        for (int x = 0, w = view.width(); x < w; x++) {
            sizes[y][x] = SIZE_NOT_COMPUTED_YET;
        }
    }
}

int size_lookup::getSize(int x, int y) {
    if (sizes[y][x] == SIZE_NOT_COMPUTED_YET) {
        calculateSize(x, y);
    }

    return sizes[y][x];
}

inline void size_lookup::calculateSize(int x, int y) {
    using namespace std;

    queue< point_t > q;
    vector< point_t > points;

    const int w = view.width();
    const int h = view.height();

    int size;

    q.push(point_t(x, y));

    // BFS algorithm is used here
    while (!q.empty()) {
        point_t p = q.front();
        q.pop();

        int c = p.x;
        int r = p.y;

        // skip points which we have already visited
        if (sizes[r][c] != SIZE_NOT_COMPUTED_YET) {
            continue;
        }

        // skip black areas
        if (view(c, r) == BLACK) {
            sizes[r][c] = SIZE_NOT_AVAILABLE;
            continue;
        }

        sizes[r][c] = SIZE_BEING_PROCESSED;

        points.push_back(p);

        for (int i = 0, l = 8; i < l; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr < 0 || nr >= h || nc < 0 || nc >= w) {
                continue;
            }

            q.push(point_t(nc, nr));
        }
    }

    size = (int) points.size();

    for (vector< point_t >::const_iterator it = points.begin(), iend = points.end();
            it != iend; ++it) {
        sizes[it->y][it->x] = size;
    }
}

}
}
}
}
}
}
